package com.hqq.exercise.math;

/**
 * CantorTable 数表问题
 * 题目描述: 如下数列 第一项1/1,第二项1/2,第三项2/1,第四项3/1,第五项2/2... 输入n 输出第n项
 * 1/1  1/2  1/3  1/4  1/5 …
 * 2/1  2/2  2/3  2/4  …
 * 3/1  3/2  3/3  …
 * 4/1  4/2  …
 * 5/1  …
 * 样例输入:
 * 3
 * 14
 * 7
 * 12345
 * 样例输出:
 * 2/1
 * 2/4
 * 1/4
 * 59/99
 * <p>
 * Created by heqianqian on 2017/8/8.
 */
public class CantorTable {

    /**
     * 获取数表中的第index项
     */
    public static int getItem(int index) {
        int k = 1, s = 0;
        while (true) {
            s += k;
            if (s >= index) {//所求项是第k条对角线的倒数第s-n+1个元素
                System.out.println((s - index + 1) + "/" + (k - s + index));
                break;
            }
            k++;
        }
        return 0;
    }

    /**
     * 获取数表中的第index项 使用平方的方法实现
     */
    public static int getItemBySqrt(int index){
        int k = (int) (Math.floor((Math.sqrt(8.0*index+1)-1)/2-1e-9)+1);
        int s = (k+1)*k/2;
        System.out.println((s - index + 1) + "/" + (k - s + index));
        return 0;
    }

}
